<?php
/**
 * Class for Tree data structures
 * DVelum project http://code.google.com/p/phpveil/ , http://dvelum.net
 * Copyright (C) 2011  Kirill A Egorov kirill.a.egorov@gmail.com
 */
class Tree
{
    protected $_items = array();
    protected $_childs = array();
    /**
     * Change item sorting order
     * @param mixed $id
     * @param integer $order
     */
    public function setItemOrder($id , $order)
    {
    	if(!$this->itemExists($id))
    		return false;
   		
    	$this->_items[$id]['order'] = $order;	
    	return true;
    }
    /**
     * Sort tree Items
     * @param mixed $parentId - optional, sort only item childs
     * default - false (resort all items)
     */
    public function sortItems($parentId = false)
    {
    	if($parentId)
    		$this->_sortChilds($parentId);
    	else
    		foreach ($this->_childs as $k=>$v)
    			$this->_sortChilds($k);	
    }
    /**
     * Check if item exists
     * @param mixed $id
     * @return boolean
     */
    public function itemExists($id)
    {
        return isset($this->_items[$id]);
    }
    /**
     * Get count of items
     * @return integer
     */
    public function getItemsCount()
    {
        return sizeof($this->_items);
    }
    /**
     * Add item to the tree
     * @param mixed $id
     * @param mixed $parent
     * @param mixed $data
     * @param integer $order - optional
     * @return boolean - success flag
     */
    public function addItem($id , $parent =0 , $data , $order = false)
    {
       if($this->itemExists($id))
           return false;

       if(!$order && isset($this->_childs[$parent]))
               $order = sizeof($this->_childs[$parent]);
                
       $this->_items[$id] = array(
            	'id'=>$id ,
                'parent'=>$parent ,
                'data'=>$data,
                'order'=>$order
        );    
        if(!isset($this->_childs[$parent]))
           $this->_childs[$parent] = array();
                
        $this->_childs[$parent][$id] = & $this->_items[$id];
        return true;
    }
    /**
     * Get item by Id
     * @param mixed $id
     * @return mixed
     */
    public function getItem($id)
    {
        if($this->itemExists($id))
            return $this->_items[$id];
         else     
             throw new Exception('Item is not found');   
    }
    /**
     * Check if item has childs
     * @param string $id
     * @return boolean
     */
    public function hasChilds($id)
    {
    	if(isset($this->_childs[$id]) && !empty($this->_childs[$id]))
    		return true;
    	else 
    		return false;
    }
    
    /**
     * Get item childs recursive
     * @var mixed id
     * @return array
     */
    public function getChildsR($id)
    {
        $data = array();
        if($this->hasChilds($id))
        {
           $childs = $this->getChilds($id);
           foreach ($childs as $k=>$v)
           {
               $data[] = $v['id'];
               $subChilds = $this->getChildsR($v['id']);
               if(!empty($subChilds))
                   $data = array_merge($data , $subChilds);
            }
         }
         return $data;
    }
    protected function _sortChilds($id)
    {
    	 if(!isset($this->_childs[$id]) || empty($this->_childs[$id]))
    		return true;
   		
    	 $tmp = array();

         foreach ($this->_childs[$id] as $key=>&$dat)
              $tmp[$dat['id']] = $dat['order'];      
         unset($dat);     
              
         $this->_childs[$id] = array();
         asort($tmp);

         foreach ($tmp as $key=>$order)
            $this->_childs[$id][$this->_items[$key]['id']] = & $this->_items[$key];	
    }
    /**
     * Get item childs
     * @var mixed id
     * @return array
     */
    public function getChilds($id)
    {   	
        if(!$this->hasChilds($id))
            return array();

        return $this->_childs[$id];
    }
    /**
     * Recursively removing
     * @param mixed $id
     * @return void
     */
    protected function _remove($id)
    {
       $item = $this->getItem($id);
       $childs = $this->getChilds($id);
       
       if(!empty($childs))
           foreach ($childs as $k=>&$v)
                $this->_remove($v['id']);

       if(isset($this->_childs[$id]))
            unset($this->_childs[$id]);
               
       $parent = $this->_items[$id]['parent'];

       if(!empty($this->_childs[$parent]) && isset($this->_childs[$parent][$id]))
            unset($this->_childs[$parent][$id]);
           
       unset($this->_items[$id]);
    }
    /**
     * Change parent node
     * @param mixed $id
     * @param mixed $newParent
     * @return void
     */
    public function changeParent($id , $newParent)
    {
        if(!$this->itemExists($id) || (!$this->itemExists($newParent) && $newParent !== 0))
        	return;
        	
        $oldParent = $this->_items[$id]['parent'];
        $this->_items[$id]['parent'] = $newParent;
        if(!empty($this->_childs[$oldParent]) && isset($this->_childs[$oldParent][$id]))
             	unset($this->_childs[$oldParent][$id]);  
             	       	
         $this->_childs[$newParent][$id] = & $this->_items[$id];  
    }
    /**
     * Remove item
     * @param mixed $id
     * @return void
     */
    public function removeItem($id)
    {
       if($this->itemExists($id))
            $this->_remove($id);     
            
       return true;
    }
    /**
     * Get All items
     * @return array
     */
    public function getItems()
    {
    	return $this->_items;
    }
}
